# -*- coding:utf-8 -*-
# py38
# 阅读哥德尔、埃舍尔、巴赫是遇到的一个问题

# 规则1：如果字符串以J结尾，可以在后面再加上一个U
#  eg: WJ => WJU
# 规则2：如果你有Wx，则可以生成Wxx
#  eg: WJ => WJJ
#     WJJ => WJJJJ
# 规则3：可以使用U代替JJJ
#  eg: WJJJ => WU
# 规则4：UU可以消除掉
#  eg: WUUJ => WJ

# 起始条件WJ，求生成WU

import queue

class Solution:
    def __init__(self, path = [], possible = set()):
        self.path = path
        self.possible = possible

    def generate_next(self):
        ret = []
        possible = []
        for p in self.possible:
            rule1 = self.build_with_rule1(p)
            if rule1 != None and rule1 not in possible:
                possible.append(rule1)
            rule2 = self.build_with_rule2(p)
            if rule2 != None and rule2 not in possible:
                possible.append(rule2)
            rule3 = self.build_with_rule3(p)
            for r in rule3:
                if r not in possible:
                    possible.append(r)
            rule4 = self.build_with_rule4(p)
            for r in rule4:
                if r not in possible:
                    possible.append(r)
        ret.append(Solution(path = self.path + [p], possible = possible))
        return ret

    def build_with_rule1(self, str):
        if len(str) <= 1:
            return None 
        if not str.endswith("J"):
            return None
        return str + "U"

    def build_with_rule2(self, str):
        if len(str) <= 1:
            return None
        if str[0] != "W":
            return None
        return str[0] + str[1:] * 2

    def build_with_rule3(self, str):
        ret = []
        index = str.find("JJJ", 0)
        while index != -1:
            n = str[0:index] + str[index:].replace("JJJ", "U", 1)
            if n not in ret:
                ret.append(n)
            index = str.find("JJJ", index + 1)
        return ret

    def build_with_rule4(self, str):
        ret = []
        index = str.find("UU", 0)
        while index != -1:
            n = str[0:index] + str[index:].replace("UU", "", 1)
            if n not in ret:
                ret.append(n)
            index = str.find("UU", index + 1)
        return ret


def build_wu(start, end):
    checked = []
    checked.append(start)
    solution_queue = queue.Queue()
    solution_queue.put(Solution(path = [], possible = [start]))
    while True:
        s = solution_queue.get()
        next_solutions = s.generate_next()
        
        if next_solutions is None:
            continue

        for solution in next_solutions:
            possible = []
            for p in solution.possible:
                if p in checked:
                    continue
                if p == end:
                    return solution.path + [end]
                possible.append(p)
                checked.append(p)
            solution.possible = possible
            solution_queue.put(solution)

# 程序写完之后发现生成WU是不可能的
# 证明如下：
# 针对J的个数
# 执行规则1之后J的数目不变[不变]
# 执行规则2之后J的数目翻倍[x2]
# 执行规则3之后J的数目-3[-3]
# 执行规则4之后J的数目不变[不变]
# 由上可知，所有规则对于J的数目的影响是[不变],[x2],[-3]
# 初始J的数目是1，结果J的数目是0
# [不变],[-3]不影响 J % 3的数值
# [x2] J % 3只会是1和2，不会变成0，所以是无法导出最终的结果的 
print(build_wu("WJ", "WU"))
